\documentclass[12pt,titlepage]{article}
\usepackage[spanish]{babel}
\usepackage[utf8]{inputenc}
%\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{graphicx}

\usepackage{color}
\usepackage{url}
\definecolor{lnk}{rgb}{0,0,0.4}
\usepackage[colorlinks=true,linkcolor=lnk,citecolor=blue,urlcolor=blue]{hyperref}

\newcommand{\func}[2]{\texttt{#1}(#2) :}
\newcommand{\tab}{\hspace*{2em}}
\newcommand{\FOR}{\textbf{for }}
\newcommand{\TO}{\textbf{ to }}
\newcommand{\IF}{\textbf{if }}
\newcommand{\WHILE}{\textbf{while }}
\newcommand{\THEN}{\textbf{then }}
\newcommand{\ELSE}{\textbf{else }}
\newcommand{\RET}{\textbf{return }}
\newcommand{\MOD}{\textbf{ \% }}
\newcommand{\OR}{\textbf{ or }}
\newcommand{\NOT}{\textbf{ not }}
\newcommand{\tOde}[1]{\tab \small{\mathcal{O}($#1$)}}
\newcommand{\Ode}[1]{\ensuremath{\small{\mathcal{O}\left(#1\right)}}}
\newcommand{\VSP}{\vspace*{3em}}
\newcommand{\Pa}{\vspace{5mm}}
\newenvironment{pseudo}{\noindent\begin{tabular}{ll}}{\end{tabular}\VSP}

\newenvironment{while}{\WHILE \\ \setlength{\leftmargin}{0em} }{}

\newcommand{\gra}[1]{\noindent\includegraphics[scale=.70]{#1}\\}
\newcommand{\gram}[1]{\noindent\includegraphics[scale=.50]{#1}}
\newcommand{\dirmail}[1]{\normalsize{\texttt{#1}}}

\title{{\sc\normalsize Algoritmos y estructuras de datos III}\\{\bf Trabajo Práctico Nº3}}
\author{\begin{tabular}{lcr}Carla Livorno & 424/08 & \dirmail{carlalivorno@hotmail.com}\\Thomas Fischer & 489/08 & \dirmail{tfischer@dc.uba.ar}\\Kevin Allekotte & 490/08 & \dirmail{kevinalle@gmail.com} \end{tabular}}
\date{\VSP \normalsize{Diciembre 2009}}
\begin{document}
\begin{titlepage}
\maketitle
\end{titlepage}
\tableofcontents
\newpage

	\begin{section}*{Introducción}	\addcontentsline{toc}{section}{Introducción}

	\end{section}

	\begin{section}{Situaciones de la vida real}

		El problema \texttt{MAX-SAT} es utilizado en la vida real en diversas áreas.
		Acá hay algunas situaciones que se pueden modelar con este problema.

		\begin{itemize}

			\item Toma de decisiones binarias, de manera de satisfacer la mayor cantidad de tareas posibles.
			
			Por ejemplo, se puede modelar un problema parecido al siguiente: se tienen ciertas tareas a realizar. Las tareas se llevan a cabo satisfaciendo alguno de sus requisitos. Los requisitos son decisiones binarias (si/no). Lo que se quiere es tomar las decisiones correctas para maximizar las tareas que se llevan a cabo.
			
			El modelo es bastante directo: las decisiones o requisitos serían las variables, y cada tarea es representada por una clausula que contiene el conjunto de las deciciones que la satisfacen.
	
			\item También es usado de la forma trivial en el área de lógica matematica, dado que el problema en sí ya está planteado en forma de lógica proposicional.
			

		\end{itemize}

	\end{section}
	
	\begin{section}*{Optimización Global}	\addcontentsline{toc}{section}{Optimización Global}
		Para mejorar un poco el desempeño de todos los algoritmos filtramos los datos de entrada para reducir un poco su tamanio sin que altere el resultado de los algoritmos.
		
		Cuando leemos la entrada buscamos las clausulas que son tautologias, es decir, las clausulas que son verdaderas sin importar el valor que le es asignado a las variables. Estas clausulas tienen a su vez un literal y su contrario. Por ejemplo, una clausula que contenga $a$ y $\neg a$ siempre es verdadera.
		
		A las clausulas de este tipo las ignoramos durante el algoritmo, pero las imprimimos como satisfechas cuando devolvemos el resultado.
	\end{section}

	\begin{section}{Algoritmo exacto}

		Para encontrar la solución exacta al problema hicimos un algoritmo que usa la técnica de backtracking que recorre todas las posibles combinaciones de asignaciónes de valores de verdad a las variables involucradas,
		calculando para cada combinación la cantidad de clausulas satisfechas y guardando registro de la mejor solución encontrada en todo momento, para así obtener con seguridad la solución óptima al finalizar el algoritmo. \\
	
		Para recorrer las soluciones seteamos una variable en falso y visitamos recursivamente todas las combinaciones de las restantes variables (las que son mayores numericamente).
		Luego la seteamos en verdadero y volvemos a visitar las combinaciones de las restantes de la misma manera.
	
		Siempre que obtenemos una solución (cuando todas las variables tienen algun valor) evaluamos si dicha solución es mejor que la máxima que teniamos hasta el momento y la actualizamos de ser necesario. \\

		Sigue un pseudocódigo que muestra el algoritmo para una instancia del problema. \\

		\begin{pseudo}
			\func{exacto}{it}							\hfill \Ode{2^v\times c\times v}\\
			\tab \IF it $<$ variables.size() :			\hfill \Ode{1}\\
			\tab \tab variables[it] $\gets$ false;		\hfill \Ode{1}\\
			\tab \tab \IF c-max\_cs $<$ clausulas\_insat(variables,it) :	\\
			\tab \tab \tab \texttt{exacto}(it+1)							\hfill \Ode{2^{v-it}}\\
			\tab \tab variables[it] $\gets$ true;		\hfill \Ode{1}\\
			\tab \tab \IF c-max\_cs $<$ clausulas\_insat(variables,it) :	\\
			\tab \tab \tab \texttt{exacto}(it+1)							\hfill \Ode{2^{v-it}}\\
			\tab \ELSE :												\\
			\tab \tab cs $\gets$ \texttt{clausulas\_satisfechas}(variables) \hfill \Ode{c\times v}\\
			\tab \tab \IF cs $>$ max\_cs :				\hfill \Ode{1}\\
			\tab \tab \tab max\_cs $\gets$ cs			\hfill \Ode{c}\\
			\tab \tab \tab max\_var $\gets$ variables 	\hfill \Ode{v}

		\end{pseudo}

		Donde \texttt{it} es la iteracion o nivel del arbol binario de combinaciones en el que se encuentra el algoritmo,
		\texttt{variables} es un arreglo del estado de las variables en cada paso del algoritmo,
		asi como \texttt{max\_variables}, con la diferencia que esta ultima guarda el arreglo que maximizo la cantidad de clausulas satisfechas hasta el momento, numero que es guardado en \texttt{max\_cs}.

		La funcion \texttt{clausulas\_satisfechas} devuelve, para un estado de las variables, la cantidad de clausulas que se satisfacen de esta manera,
		y \texttt{clausulas\_insat} la cantidad de clausulas que con seguridad no se satisfacen con las variables seteadas hasta la \texttt{it}.
		
		\begin{subsection}{Optimizacion}
			Incluimos además una optimización para mejorar un poco el tiempo de ejecución. Si bien el algoritmo es exponencial, se deben realizar todas las optimizaciones posibles para que resuelva instancias relativamente chicas en un tiempo aceptable.
			
			Dado que se trata de un algoritmo de backtracking, la optimzación se basa en podar las ramas en las que estamos seguros que no va a aparecer el óptimo. Para esto tenemos que poder predecir, dado un estado actual, si es posible mejorar el óptimo encontrado hasta el momento.
			
			Para esto, evaluamos en cada paso del algoritmo la cantidad de clausulas insatisfacibles. Es decir, contamos las clausulas que seguramente no van a podes ser cumplidas dado el valor que asignamos a las variables hasta ese momento. Si la cantidad de clausulas insatisfacibles es mayor a la cantidad de clausulas menos el maximo de clausulas satisfacible hasta el momento, no tiene sentido seguir explorando esa rama, y se la poda.
		\end{subsection}

		\begin{subsection}{Complejidad temporal}	

			El costo de calcular la cantidad de clausulas que satisface una solución es $\sum_{i=1}^v c(v) \leq c\times v$ ya que recorremos las variables y por cada una de estas las clausulas que satisface. Por lo que la complejidad de la función \texttt{clausulas\_sat} es \Ode{c\times v}.

			Para cada variable hay dos opciones (verdadero o falso) por lo que la complejidad de entontrar todas las combinaciones es $2^v$ donde $v$ es la cantidad de variables.

			Dado que cada vez que obtenemos una solución la comparamos con la que tenemos hasta el momento el costo del algoritmo es
			el costo de encontrar la combinación por el costo de compararla, es decir, la complejidad de \texttt{exacto} es \Ode{2^v\times c\times v}.

		\end{subsection}
	
	\end{section}

	\begin{section}{Heurística constructiva}

		Como Primera Heurística, en este caso constructiva, desarrollamos un algoritmo para resolver el problema \texttt{MAX-SAT} de manera aproximada que funciona de la siguiente manera. \\

		A cada variable le asignamos un valor de verdad el cual no vuelve a cambiar. Además llevamos registro de las cláusulas que fueron satisfechas hasta el momento.

		El criterio de decisión para asignar dicho valor a la variable, es elegir aquel valor de verdad que mas cláusulas haga verdaderas de aquellas que todavía no lo son en estado actual del algoritmo.

		Al final del algoritmo todas las variables tienen un valor definido. \\

		El siguiente es un pseudocodigo del algoritmo para una instancia del problema. \\

		\begin{pseudo}

			\func{constructiva}{}	\hfill \Ode{c \times v}\\
			\tab \FOR v $\gets$ 0 \TO variables.size() :	\hfill \Ode{c \times v}\\
			\tab \tab mejor\_valor $\gets$ \texttt{satisface}(v,true) $>$ \texttt{satisface}(v,false)	\hfill \Ode{c(v)}\\
			\tab \tab variables[v] $\gets$ mejor\_valor	\hfill \Ode{1}\\
			\tab \tab \texttt{actualizar\_clausulas}(v,mejor\_valor)	\hfill \Ode{c}

		\end{pseudo}

		Donde \texttt{variables} es un arreglo que guarda el estado de cada variable (verdadera o falsa)
		y \texttt{clausulas} es otro arreglo que guarda el estado de cada clausula (satisfecha o no).

		La funcion \texttt{satisface} devuelve, dada una variable y un valor de verdad, cuantas de las clausulas insatisfechas satisface esa variable con ese valor.

		La funcion \texttt{actualizar\_clausulas} actualiza el arreglo de clausulas en funcion del nuevo valor de verdad elegido para la variable.

		\begin{subsection}{Complejidad temporal}
		
			Tenemos la función \texttt{satisface} para calcular la cantidad de clausulas que puede satisfacer un literal, es decir, las clausulas a las que dicho literal pertenece y todavia no estan satisfechas. El costo de dicha función es \Ode{c(v)} donde $c(v)$ es la cantidad de clausulas a la que pertenece el literal v.

			Para cada variable decidimos llamando a la función \texttt{satisface} si es mejor (satisface más clausulas) setearla en verdadero o en falso y marcamos como satisfechas las clausulas a las que pertenece la variable con el valor de verdad que le dimos.

			La complejidad del algoritmo es $$\Ode{\sum_{v=0}^{\#V}{2\times c(v)}} \subseteq \Ode{\sum_{v=0}^{\#V}{2\times c}} \subseteq \Ode{2\times v\times c} \subseteq \Ode{c\times v}$$
			
			El tiempo de ejecución no depende cualitativamente de la entrada, ya que realiza siempre el mismo procedimiento que sólo depende de la cantidad de variables totales y de la cantidad de clausulas a las que pertenece cada variable. Por lo tanto los peores casos para este algoritmo son los que maximizan $\sum_{v=0}^{\#V}{2\times c(v)}$.

		\end{subsection}

	\end{section}

	\begin{section}{Busqueda local}

			Luego, presentamos una heurística con un concepto distinto, de búsqueda local, que actúa a partir de una solución inicial $S$.
			Este algoritmo busca en la vecindad de la solución dada, $N(S)$, una solución mejor que ésta.
			Si no encuentra ninguna mejor, nos encontramos en un óptimo local (de la vecindad), que tomamos como óptimo y la tomamos como solución del algoritmo.
			Si encontramos una solución mejor, repetimos el proceso partiendo de esta nueva solución.
			
			Decidimos revisar toda la vecindad $N(S)$ en cada iteración y quedarnos con el vecino máximo. De esta manera llegamos al optimo local por la 'máxima pendiente'. La otra opción era quedarse con el primer vecino que es mayor que el actual, pero la complejidad es la misma y creemos que revisar todos da mejores resultados.

			La vecindad $N(S)$ en este problema la tomamos como las soluciónes que difieren únicamente en el valor de una sola variable.
			Luego para revisar la vecindad, cambiamos el valor de cada una de las variables a partir del óptimo actual, y comparamos la cantidad de clausulas que quedan satisfechas de esta manera con la cantidad que satisfacía el óptimo.
			Si la nueva solución es mejor, pasa a ser el óptimo actual.
			Al final de recorrer la vecindad, tenemos un nuevo óptimo local con el cuál repetir el proceso.

			El pseudocódigo correspondiente al algoritmo para una instancia del problema sería el siguiente. \\

			\begin{pseudo}

				\func{busqueda\_local}{}	\hfill \Ode{c^2\times v^2}\\
				\tab variables $\gets$ \texttt{solucion\_inicial}()	\hfill \Ode{c\times v}\\

				\tab nuevo\_max $\gets$ true	\hfill \Ode{1}\\
				\tab max\_cs $\gets$ \texttt{clausulas\_satisfechas}(variables)	\hfill \Ode{c\times v}\\

				\tab \WHILE nuevo\_max	\hfill \Ode{c^2\times v^2}\\
				\tab \tab nuevo\_max = false	\hfill \Ode{1}\\
				\tab \tab \FOR i $\gets$ 0 \TO variables.size() :	\hfill \Ode{c\times v^2}\\
				\tab \tab \tab variables[i] $\gets$ \NOT variables[i]	\hfill \Ode{1}\\
				\tab \tab \tab cs $\gets$ \texttt{clausulas\_satisfechas}(variables)	\hfill \Ode{c\times v}\\

				\tab \tab \tab \IF cs $>$ max\_cs :	\hfill \Ode{1}\\
				\tab \tab \tab \tab max\_cs = cs	\hfill \Ode{1}\\
				\tab \tab \tab \tab nuevo\_max = true	\hfill \Ode{1}\\
				\tab \tab \tab \tab flip\_que\_optimiza $\gets$ i	\hfill \Ode{1}\\
				%\tab \tab \tab \tab break											\\
				%\tab \tab \tab \ELSE :												\\
				\tab \tab \tab variables[i] $\gets$ \NOT variables[i]	\hfill \Ode{1}\\
				\tab \tab \IF nuevo\_max:	\hfill \Ode{1}\\
				\tab \tab \tab variables[flip\_que\_optimiza] $\gets$ \NOT variables[flip\_que\_optimiza]	\hfill \Ode{1}\\

			\end{pseudo}

			\texttt{variables} es un arreglo que guarda el estado de cada variable.
			Al principio y al final de cada iteración del algoritmo, las mismas se corresponden con el valor en max\_cs, o sea, es la asignación de valores para el cuál la cantidad de clausulas satisfechas resulto maxima hasta el momento.

			La funcion \texttt{clausulas\_satisfechas} calcula la cantidad de clausulas satisfechas dada una asignacion de valores de las variables.

			\texttt{nuevo\_max} esta en true si hay una solucion maxima cuya vecindad N(variables) aún no ha sido revisada.

			\texttt{max\_cs} guarda el máximo valor de clausulas satisfechas encontrado.

		\begin{subsection}{Complejidad temporal}	

			El costo de calcular la cantidad de clausulas que satisface una solución es $\sum_{i=1}^v c(v) \leq c\times v$ ya que recorremos las variables y por cada una de estas las clausulas que satisface. Por lo que la complejidad de la función \texttt{clausulas\_satisfechas} es \Ode{c\times v}.
		
			Como el algoritmo parte de la solución de la heuristica constructiva el costo del mismo es calcular dicha solución \Ode{c\times v} más calcular la cantidad de clausulas que satisface \Ode{c\times v} más el costo de la función principal (revisa la vecindad y actualiza el máximo) que se detalla a continuación.

			Prueba para cada variable cambiarle el valor de verdad que tiene en la solución actual calculando con cada cambio la cantidad de clausulas que satisface la nueva solución (llamando a la función \texttt{clausulas\_satisfechas}). Si la solución mejoró, la toma como nueva solución y repite el proceso. Esto cuesta \Ode{v\times \texttt{clausulas\_satisfechas}}, es decir, \Ode{v\times c\times v} = \Ode{c\times v^2}.

			Repite el proceso antes mencionado tantas veces como la solución mejore, esto puede pasar a lo sumo $c$ veces ya que en el peor caso con cada mejora logra satisfacer una clausula.
		
			La complejidad de la busqueda local es \Ode{c\times v + c\times v + c^2\times v^2} = \Ode{c^2\times v^2}.
			
			\medskip
			
			En este caso el tiempo de ejecucón del algoritmo sí depende cualitativamente de la entrada y no solo del tamaño. Si bien la complejidad calculada es una cota superior para el tiempo de ejecución confiamos en que el algoritmo funciona mucho mejor en la mayoria de los casos.
			
			Esto se debe a que itera mientras la solucion mejore respecto a la anterior. Podría pasar que la heurística constructiva ya encuentre una solución que es óptima en su vecindad y en ese caso la búsqueda local hace una sola iteración. Tambien podría pasar que en la vecindad siempre encuentre una solución apenas mejor (que satisfaga sólo una clausula más). Este tipo de caso es muy improbable, pero hace posible la peor complejidad del algoritmo y por lo tanto constituye el peor caso para esta heurística.
	
		\end{subsection}

	\end{section}

	\begin{section}{Tabu-Search}

		Finalmente implementamos una metaheuristica, es decir, una heurística que guía otra heurística, en este caso la búsqueda local del ejercicio anterior.

		El \texttt{Tabu-Search} permite evitar que la heurística de búsqueda local se estanque en óptimos locales cuando en realidad fuera de la vecindad existía una solución óptima global (mejor que la local).
		Para lograrlo, permite al algoritmo perseguir una solución peor que la mejor obtenida mediante búsqueda local, por una cantidad máxima de iteraciones.
		Pasada esta cantidad, consideramos que el algoritmo ya busco lo suficiente y la mejor solución encontrada hasta el momento debe ser la óptima. \\

		Para no revisar las vecindades que se revisaron anteriormente (que son muy cercanas a la vecindad actual),
		cada vez que decidimos movernos a otra vecindad porque tenemos un nuevo aspirante a óptimo (mas alla de que sea peor que la mejor solución que encontramos hasta el momento, pero lo llamamos así por su similitud con el mismo en la búsqueda local)
		prohibimos revertir el cambio que hicimos para llegar del aspirante anterior al nuevo, o sea, prohibimos flippear el valor de verdad de una variable.

		Esto lo implementamos mediante un arreglo de variables, donde para cada variable guardamos la iteracion en que la misma deja de ser tabú (el algoritmo lleva la cuenta de las iteraciones).
		Luego cuando revisamos las vecindades de un aspirante, evitamos aquellas donde la modificación implica cambiar una variable tabú. \\

		\begin{pseudo}
			\func{tabu\_search}{}	& \Ode{c^2\times v^2}\\
			\tab iteracion $\gets$ 1\\
			\tab \WHILE iteracion $<$ last\_max\_iter + MAX\_ITER :										\\
			\tab \tab local\_max\_cs $\gets$ -1													\\
			%\tab \tab local\_max\_var																	\\
			\tab \tab \FOR i $\gets$ 0 \TO variables.size():	& \Ode{c\times v^2}\\
			\tab \tab \tab \IF \NOT \texttt{esta\_tabu}(i) :	& \Ode{1}\\
			\tab \tab \tab \tab variables[i] $\gets$ \NOT variables[i]	\\
			\tab \tab \tab \tab cs $\gets$ \texttt{clausulas\_satisfechas}(variables)	& \Ode{c\times v}\\
			\tab \tab \tab \tab \IF cs $>$ local\_max\_cs :\\
			\tab \tab \tab \tab \tab local\_max\_cs $\gets$ cs\\
			\tab \tab \tab \tab \tab local\_max\_var $\gets$ i\\
			\tab \tab \tab \tab variables[i] $\gets$ \NOT variables[i]\\
			\tab \tab variables[local\_max\_var] $\gets$ \NOT variables[local\_max\_var]\\
			\tab \tab tabu[local\_max\_var] $\gets$ iteracion + TABU\_ITER\\
			\tab \tab \IF local\_max\_cs $>$ max\_cs :													\\
			\tab \tab \tab max\_cs $\gets$ local\_max\_cs											\\
			\tab \tab \tab max\_var $\gets$ variables												\\
			\tab \tab \tab last\_max\_iter $\gets$ iteracion										\\
			\tab \tab iteracion$\gets$ iteracion+1																		\\
		\end{pseudo}

		\begin{subsection}{Complejidad temporal}	

			El costo de calcular la cantidad de clausulas que satisface una solución es $\sum_{i=1}^v c(v) \in \Ode{c\times v}$ ya que recorremos las variables y por cada una de estas las clausulas que satisface. Por lo que la complejidad de la función \texttt{clausulas\_sat} es \Ode{c\times v}.
			
			Como el algoritmo parte de la solución de la heuristica constructiva el costo del mismo es calcular dicha solución \Ode{c\times v} más calcular la cantidad de clausulas que satisface \Ode{c\times v} más el costo de la función principal (revisa la vecindad y actualiza el máximo) que se detalla a continuación.

			Para cada variable que no pertenece a la lista tabu, cambia su valor de verdad y calcula con \texttt{clausulas\_sat} la cantidad de clausulas satisfechas. Si la solución mejoro la actualiza y sigue buscando soluciones locales. Sino revierte el cambio.
			Esto lo repite a lo sumo tantas veces como variables haya por la constante $MAX\_ITER$, ya que dicha variables es el plazo que se le da al algortimo para encontrar una mejor solución. En el peor de los casos cada $MAX\_ITER$ iteraciones el algoritmo mejora la solución en solo una clausula.

			Por lo que la complejidad del algoritmo es \Ode{c\times v + c\times v + MAX\_ITER\times c^2\times v^2} = \Ode{MAX\_ITER\times c^2\times v^2} = \Ode{c^2\times v^2}
			
			\medskip
			
			Al igual que la búsqueda local, esta es una cota superior muy suelta para la complejidad del algoritmo. Esto se debe a que el tiempo de ejecución depende mucho de lo que el algoritmo se va encontrando en el camino, y no tanto del tamaño de la entrada.
			
			Acá también, los casos que producen que el algoritmo se comporte temporalmente como la cota son muy improbables y no son tan fáciles de categorizar. Lo que tendría que pasar es que el algoritmo encuentre una solución apenas mejor cada $MAX\_ITER-1$ iteraciones. Esto también depende de la forma en la que \texttt{tabu search} recorre el espacio de soluciones, entonces podría diferir mucho el tiempo de ejecución incluso para instancias muy parecidas.
		
		\end{subsection}

	\end{section}

	\begin{section}{Adicional}

		\begin{subsection}{Heuristica constructiva mejorada}

			Desarrollamos otra heuristica constructiva para resolver el problema \texttt{MAX-SAT}.
			El funcionamiento de la misma es el siguiente.
			
			En cada paso del algoritmo elegimos el valor que va a tomar alguna de las variables en el problema, y esto lo hacemos tantas veces como variables involucradas existan.
			Luego al final del algoritmo todas las variables tienen un valor definido.

			El criterio de decisión para asignar un valor a una variable, es elegir aquel literal que mas cláusulas satisfaga,
			de las que todavía no fueron satisfechas en el estado actual del algoritmo.

			Tenemos en primer lugar una estructura dinámica donde guardamos inicialmente todos los literales asociados con la cantidad de cláusulas que satisfacen en el estado del algoritmo.
			También tenemos una lista con el estado de las variables, y otro con el estado de las cláusulas.
			En cada paso del algoritmo, tomamos el máximo de la primera estructura y lo eliminamos de ella, como también al literal que representa al máximo negado.
			Luego asignamos el valor que corresponda a la variable y actualizamos el arreglo de clausulas satisfechas.
			También marcamos en la primer estructura, para cada literal, que las cáusulas satisfechas ya no son satisfacibles por los mismos.

		\end{subsection}

	\end{section}
	
	\begin{section}{Resultados}

		\begin{subsection}{Parametros de la heurística tabú}

			\gra{TABU_ITER.png}
		
			\gra{MAX_ITER.png}
			

			La heurística tabú hace uso de dos parametros, los cuáles tuvimos que ajustar de manera de conseguir los mejores resultados.

			Estos parámetros son la cantidad de tiempo (iteraciones) que una variable permanece tabú, que llamamos \texttt{TABU\_ITER},
			y la cantidad de tiempo (iteraciones) que se esperan antes de cortar el algoritmo si no encuentra un nuevo máximo, que llamamos \texttt{MAX\_ITER}.

			El gráfico de arriba muestra la cantidad de clausulas satisfechas por el algoritmo para los distintos valores del parametro TABU\_ITER entre 1 y 100.
			Al observar que el algoritmo se estanca a partir de valores muy bajos no decidimos mirar para valores mas altos.
			
			En el segundo grafico se muestra el desempeño del algoritmo segun distintos valores de \texttt{MAX\_ITER}. Se observa que es constante con valores por encima de 6.

			Para TABU\_ITER nos decidimos por el valor 6 y para MAX\_ITER por el 10, despues de ver los resultados a los que corresponden los graficos.

		\end{subsection}		

		\begin{subsection}{Comparacion de tiempos}

			\gra{tiempos_todos_vs_exacto.png}

			En la figura, se ven graficados los distintos tiempos de ejecución de los algoritmos en función del algoritmo exacto.

			Se puede apreciar el parecido de la curva del tabú search con el gráfico de una funcion logarítmica,
			lo cuál concuerda con los resultados que esperabamos, ya que el algoritmo exacto era exponencial,
			y se requiere una transformación de tipo logarítmica (o parecida) para tener un algoritmo polinomial.

			La heurística constructiva y la de búsqueda local son claramente superiores en tiempos de ejecución, pero la calidad de la solución no es tan buena, como se ve en los próximos items.

		\end{subsection}

		\begin{subsection}{Comparacion de calidad}

			\gra{plot_todos_vs_exacto.png}

			En la figura de arriba graficamos la optimalidad de los distintos algoritmos para entradas relativamente chicas (maximo 24 Variables, 30 Clausulas, 5 Variables por clausula). El eje \texttt{X} representa la cantidad de clausulas satisfacibles (segun el algoritmo exacto), y el eje \texttt{Y} representa la cantidad de clausulas satisfechas por los distintos algoritmos.

			Se observa que el \texttt{Tabu search} es óptimo para la mayoria de las instancias y que la busqueda local y la heuristica constructiva mejoran conforme crece la cantidad de clausulas satisfacibles.

			\gra{plot_todos_vs_tabu.png}

			En esta figura graficamos los resultados de los distintos algoritmos para entradas mas grandes. Como no sabemos la cantidad exacta de clausulas satisfacibles lo graficamos en funcion de la cantidad de clausulas que pudo satisfacer el \texttt{Tabu Search}.

			Se observa que la busqueda local es mejor quue la constructiva en muchos casos pero nunca se supera la solucion del tabu.

		\end{subsection}

	\end{section}


	\begin{section}{Compilación y ejecución de los programas}	

		Para compilar los ejercicios, pararse en el directorio \texttt{src} con una consola y ejecutar el comando \texttt{make}.
		El mismo compilará los binarios ejecutables (\texttt{X}) a partir de los fuentes (\texttt{X.cpp}).

		Para ejecutar el binario de un ejercicio, siturarse con una consola en el directorio donde se compilo (\texttt{src})
		y correrlo asignando por la entrada standardt un archivo de entrada y opcionalmente direccionando la salida standardt a un archivo de salida.
		\texttt{'./X < Y.in > Z.out'}, donde X es el nombre del ejecutable, Y el nombre del archivo de entrada y Z el de salida.

	\end{section}
	
	\begin{section}{Conclusiones}

		En los resultados que comparan las heurísticas con el algoritmo exacto, vemos claramente que el algoritmo \texttt{Tabu-search} da excelentes resultados para esos tamaños de entrada, ya que en muy pocos casos difiere del exacto.

		Lamentablemente para valores de entrada más grandes nos es imposible compararlos ya que correr el algoritmo exacto para esos tamaños de entrada requiere un esfuerzo computacional muy grande. Por esto existen las heurísticas.
		El costo temporal de las mismas es mucho menor (en particular ya no es exponencial sino que pasa a ser polinomial) y nos permite correr el algoritmo para entradas muy grandes resignando exactitud.

		Suponemos que el tamaño de la entrada no debería tener tanta influencia sobre la calidad del algoritmo, sino la distribucion de las variables en las cláusulas.
		Como probamos para muchos tipos de combinaciones distintas, lo único que cambiamos es la cantidad de clausulas y variables para entradas mas grandes.

		Por esto podemos suponer que la calidad del algoritmo sigue siendo excelente para valores de entrada muy grandes que ya no son comparables con la solución óptima porque no la tenemos.	

	\end{section}

\end{document}

